package it.storm.solution;

/**
 * 1893. 检查是否区域内所有整数都被覆盖
 * https://leetcode-cn.com/problems/check-if-all-the-integers-in-a-range-are-covered/
 */
public class Solutions_1893 {
    public static void main(String[] args) {
        int[][] ranges = {{1, 2}, {3, 4}, {5, 6}};
        int left = 2,  right = 5;  // output: true

//        int[][] ranges = {{1, 10}, {10, 20}};
//        int left = 21,  right = 21;  // output: false

//        int[][] ranges = {{25, 42}, {7, 14}, {2, 32}, {25, 28}, {39, 49}, {1, 50}, {29, 45}, {18, 47}};
//        int left = 15,  right = 38;  // output: true

        boolean result = isCovered(ranges, left, right);
        System.out.println(result);
    }

    /**
     * 解题思路：差分数组
     */
    public static boolean isCovered(int[][] ranges, int left, int right) {
        // 为什么长度设置为 52？因为共 50 个数，且需要往 51 下标上设置值
        int[] arr = new int[52];
        // 根据 ranges 设置差分数组
        for (int[] range : ranges) {
            int start = range[0], end = range[1];
            arr[start] ++;
            arr[end + 1] --;
        }

        for (int i = 1; i < arr.length; i++) {
            // 累加次数
            arr[i] += arr[i - 1];
        }
        for (int i = left; i <= right; i++) {
            if (arr[i] < 1) {
                // 该位置未设置值
                return false;
            }
        }
        return true;
    }
}
